<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no"><title>HashMap-JDK8源码讲解及常见面试题 | 风祈的时光录</title><meta name="keywords" content="Java集合，HashMap。"><meta name="author" content="youthlql"><meta name="copyright" content="youthlql"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="HashMap-JDK8源码讲解及常见面试题。">
<meta property="og:type" content="article">
<meta property="og:title" content="HashMap-JDK8源码讲解及常见面试题">
<meta property="og:url" content="https://imlql.cn/post/cbc5672a.html">
<meta property="og:site_name" content="风祈的时光录">
<meta property="og:description" content="HashMap-JDK8源码讲解及常见面试题。">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://upyunimg.imlql.cn/lql_static@latest/logo/java.png">
<meta property="article:published_time" content="2020-11-01T02:22:05.000Z">
<meta property="article:modified_time" content="2022-07-24T11:02:09.800Z">
<meta property="article:author" content="youthlql">
<meta property="article:tag" content="Java集合">
<meta property="article:tag" content="HashMap">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://upyunimg.imlql.cn/lql_static@latest/logo/java.png"><link rel="shortcut icon" href="https://npm.elemecdn.com/youthlql@1.0.8/blog/favicon.png"><link rel="canonical" href="https://imlql.cn/post/cbc5672a"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//hm.baidu.com"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://npm.elemecdn.com/@fortawesome/fontawesome-free@6/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://npm.elemecdn.com/@fancyapps/ui/dist/fancybox.css" media="print" onload="this.media='all'"><script>var _hmt = _hmt || [];
(function() {
  var hm = document.createElement("script");
  hm.src = "https://hm.baidu.com/hm.js?f693ff99cc7e613b88cf5b729a14b48b";
  var s = document.getElementsByTagName("script")[0]; 
  s.parentNode.insertBefore(hm, s);
})();
</script><script>const GLOBAL_CONFIG = { 
  root: '/',
  algolia: undefined,
  localSearch: {"path":"search.xml","languages":{"hits_empty":"找不到您查询的内容：${query}"}},
  translate: {"defaultEncoding":2,"translateDelay":0,"msgToTraditionalChinese":"繁","msgToSimplifiedChinese":"簡"},
  noticeOutdate: undefined,
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: false,
    post: false
  },
  runtime: '天',
  date_suffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: undefined,
  lightbox: 'fancybox',
  Snackbar: undefined,
  source: {
    justifiedGallery: {
      js: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery@2/dist/fjGallery.min.js',
      css: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery@2/dist/fjGallery.min.css'
    }
  },
  isPhotoFigcaption: false,
  islazyload: true,
  isAnchor: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: 'HashMap-JDK8源码讲解及常见面试题',
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2022-07-24 19:02:09'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(win=>{
    win.saveToLocal = {
      set: function setWithExpiry(key, value, ttl) {
        if (ttl === 0) return
        const now = new Date()
        const expiryDay = ttl * 86400000
        const item = {
          value: value,
          expiry: now.getTime() + expiryDay,
        }
        localStorage.setItem(key, JSON.stringify(item))
      },

      get: function getWithExpiry(key) {
        const itemStr = localStorage.getItem(key)

        if (!itemStr) {
          return undefined
        }
        const item = JSON.parse(itemStr)
        const now = new Date()

        if (now.getTime() > item.expiry) {
          localStorage.removeItem(key)
          return undefined
        }
        return item.value
      }
    }
  
    win.getScript = url => new Promise((resolve, reject) => {
      const script = document.createElement('script')
      script.src = url
      script.async = true
      script.onerror = reject
      script.onload = script.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        script.onload = script.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(script)
    })
  
      win.activateDarkMode = function () {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = function () {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
          if (t === 'dark') activateDarkMode()
          else if (t === 'light') activateLightMode()
        
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
    const detectApple = () => {
      if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
        document.documentElement.classList.add('apple')
      }
    }
    detectApple()
    })(window)</script><link rel="stylesheet" href="https://npm.elemecdn.com/lql_static@latest/butterfly_static/css/ali_icon.css"><link rel="stylesheet" href="https://npm.elemecdn.com/lql_static@latest/butterfly_static/css/2-24-mogai.css"><meta name="generator" content="Hexo 5.4.0"><link rel="alternate" href="/atom.xml" title="风祈的时光录" type="application/atom+xml">
</head><body><div id="web_bg"></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src= "" data-lazy-src="https://npm.elemecdn.com/lql_static@latest/avatar/2.jpg" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data is-center"><div class="data-item"><a href="/archives/"><div class="headline">文章</div><div class="length-num">37</div></a></div><div class="data-item"><a href="/tags/"><div class="headline">标签</div><div class="length-num">21</div></a></div><div class="data-item"><a href="/categories/"><div class="headline">分类</div><div class="length-num">13</div></a></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw iconfont icon-shouyex"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw iconfont icon-zuixinwenzhang_huaban"></i><span> 找文章</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/categories/"><i class="fa-fw iconfont icon-fenlei1"></i><span> 分类</span></a></li><li><a class="site-page child" href="/tags/"><i class="fa-fw iconfont icon-biaoqian1"></i><span> 标签</span></a></li><li><a class="site-page child" href="/archives/"><i class="fa-fw iconfont icon-shijianzhou"></i><span> 归档</span></a></li></ul></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('https://upyunimg.imlql.cn/lql_static@latest/logo/java.png')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">风祈的时光录</a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw iconfont icon-shouyex"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw iconfont icon-zuixinwenzhang_huaban"></i><span> 找文章</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/categories/"><i class="fa-fw iconfont icon-fenlei1"></i><span> 分类</span></a></li><li><a class="site-page child" href="/tags/"><i class="fa-fw iconfont icon-biaoqian1"></i><span> 标签</span></a></li><li><a class="site-page child" href="/archives/"><i class="fa-fw iconfont icon-shijianzhou"></i><span> 归档</span></a></li></ul></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">HashMap-JDK8源码讲解及常见面试题</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2020-11-01T02:22:05.000Z" title="发表于 2020-11-01 10:22:05">2020-11-01</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2022-07-24T11:02:09.800Z" title="更新于 2022-07-24 19:02:09">2022-07-24</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/Java%E9%9B%86%E5%90%88/">Java集合</a><i class="fas fa-angle-right post-meta-separator"></i><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/Java%E9%9B%86%E5%90%88/HashMap/">HashMap</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">4.6k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>19分钟</span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><blockquote>
<p>JDK7说过的东西，本篇文章不再讲解</p>
</blockquote>
<h1 id="数据结构"><a href="#数据结构" class="headerlink" title="数据结构"></a>数据结构</h1><h2 id="红黑树"><a href="#红黑树" class="headerlink" title="红黑树"></a>红黑树</h2><p>在JDK8中，优化了HashMap的数据结构，引入了红黑树。即HashMap的数据结构：数组+链表+红黑树。HashMap变成了这样。</p>
<img src= "" data-lazy-src="https://upyunimg.imlql.cn/youthlql@1.0.8/Java_collection/HashMap/JDK8/0001.png">

<h3 id="为什么要引入红黑树"><a href="#为什么要引入红黑树" class="headerlink" title="为什么要引入红黑树"></a>为什么要引入红黑树</h3><p>1、主要是为了提高HashMap的性能，即解决发生hash冲突后，因为链表过长而导致索引效率慢的问题</p>
<p>2、链表的索引速度是O(n)，而利用了红黑树快速增删改查的特点，时间复杂度就是O(logn)。</p>
<h2 id="Node类"><a href="#Node类" class="headerlink" title="Node类"></a>Node类</h2><p><code>HashMap</code>中的数组元素，链表节点均采用<code>Node</code>类 实现，与 <code>JDK 1.7</code> 的对比（<code>Entry</code>类），仅仅只是换了名字。</p>
<p>就是一些常规的方法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">/** </span></span><br><span class="line"><span class="comment">  * Node  = HashMap的内部类，实现了Map.Entry接口，本质是 = 一个映射(键值对)</span></span><br><span class="line"><span class="comment">  * 实现了getKey()、getValue()、equals(Object o)和hashCode()等方法</span></span><br><span class="line"><span class="comment">  **/</span>  </span><br><span class="line">  <span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; <span class="keyword">implements</span> <span class="title">Map</span>.<span class="title">Entry</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; </span>&#123;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">final</span> <span class="keyword">int</span> hash; </span><br><span class="line">        <span class="keyword">final</span> K key; </span><br><span class="line">        V value; </span><br><span class="line">        Node&lt;K,V&gt; next;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 构造方法</span></span><br><span class="line">        Node(<span class="keyword">int</span> hash, K key, V value, Node&lt;K,V&gt; next) &#123;</span><br><span class="line">            <span class="keyword">this</span>.hash = hash;</span><br><span class="line">            <span class="keyword">this</span>.key = key;</span><br><span class="line">            <span class="keyword">this</span>.value = value;</span><br><span class="line">            <span class="keyword">this</span>.next = next;</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> K <span class="title">getKey</span><span class="params">()</span>        </span>&#123; <span class="keyword">return</span> key; &#125;  </span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> V <span class="title">getValue</span><span class="params">()</span>      </span>&#123; <span class="keyword">return</span> value; &#125; </span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> String <span class="title">toString</span><span class="params">()</span> </span>&#123; <span class="keyword">return</span> key + <span class="string">&quot;=&quot;</span> + value; &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> V <span class="title">setValue</span><span class="params">(V newValue)</span> </span>&#123;</span><br><span class="line">            V oldValue = value;</span><br><span class="line">            value = newValue;</span><br><span class="line">            <span class="keyword">return</span> oldValue;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">hashCode</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">return</span> Objects.hashCode(key) ^ Objects.hashCode(value);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">boolean</span> <span class="title">equals</span><span class="params">(Object o)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">if</span> (o == <span class="keyword">this</span>)</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">            <span class="keyword">if</span> (o <span class="keyword">instanceof</span> Map.Entry) &#123;</span><br><span class="line">                Map.Entry&lt;?,?&gt; e = (Map.Entry&lt;?,?&gt;)o;</span><br><span class="line">                <span class="keyword">if</span> (Objects.equals(key, e.getKey()) &amp;&amp;</span><br><span class="line">                    Objects.equals(value, e.getValue()))</span><br><span class="line">                    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="TreeNode类"><a href="#TreeNode类" class="headerlink" title="TreeNode类"></a>TreeNode类</h2><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"></span><br><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="class"><span class="keyword">class</span> <span class="title">TreeNode</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; <span class="keyword">extends</span> <span class="title">LinkedHashMap</span>.<span class="title">Entry</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; </span>&#123;  </span><br><span class="line"></span><br><span class="line">	<span class="comment">// 属性 = 父节点、左子树、右子树、删除辅助节点 + 颜色</span></span><br><span class="line">  TreeNode&lt;K,V&gt; parent;  </span><br><span class="line">  TreeNode&lt;K,V&gt; left;   </span><br><span class="line">  TreeNode&lt;K,V&gt; right;</span><br><span class="line">  TreeNode&lt;K,V&gt; prev;   </span><br><span class="line">  <span class="keyword">boolean</span> red;   </span><br><span class="line"></span><br><span class="line">  <span class="comment">// 构造函数</span></span><br><span class="line">  TreeNode(<span class="keyword">int</span> hash, K key, V val, Node&lt;K,V&gt; next) &#123;  </span><br><span class="line">      <span class="keyword">super</span>(hash, key, val, next);  </span><br><span class="line">  &#125;  </span><br><span class="line"></span><br><span class="line">  <span class="comment">// 返回当前节点的根节点  </span></span><br><span class="line">  <span class="function"><span class="keyword">final</span> TreeNode&lt;K,V&gt; <span class="title">root</span><span class="params">()</span> </span>&#123;  </span><br><span class="line">      <span class="keyword">for</span> (TreeNode&lt;K,V&gt; r = <span class="keyword">this</span>, p;;) &#123;  </span><br><span class="line">          <span class="keyword">if</span> ((p = r.parent) == <span class="keyword">null</span>)  </span><br><span class="line">              <span class="keyword">return</span> r;  </span><br><span class="line">          r = p;  </span><br><span class="line">      &#125;  </span><br><span class="line">  &#125; </span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="重要参数"><a href="#重要参数" class="headerlink" title="重要参数"></a>重要参数</h2><blockquote>
<p>JDK7里讲过的就不再讲了</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">  <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> DEFAULT_INITIAL_CAPACITY = <span class="number">1</span> &lt;&lt; <span class="number">4</span>; </span><br><span class="line"> </span><br><span class="line">  <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> MAXIMUM_CAPACITY = <span class="number">1</span> &lt;&lt; <span class="number">30</span>; </span><br><span class="line"></span><br><span class="line">  <span class="keyword">final</span> <span class="keyword">float</span> loadFactor; </span><br><span class="line"> </span><br><span class="line">  <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">float</span> DEFAULT_LOAD_FACTOR = <span class="number">0.75f</span>; </span><br><span class="line"></span><br><span class="line">  <span class="keyword">int</span> threshold;</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 存储数据的Node类型 数组，长度 = 2的幂；</span></span><br><span class="line">  <span class="keyword">transient</span> Node&lt;K,V&gt;[] table;  </span><br><span class="line">  <span class="keyword">transient</span> <span class="keyword">int</span> size;</span><br><span class="line">  </span><br><span class="line">  <span class="comment">//与红黑树相关的参数</span></span><br><span class="line">  </span><br><span class="line">  <span class="comment">/*</span></span><br><span class="line"><span class="comment">  1、单链表(桶)的树化阈值：即 链表转成红黑树的阈值，在存储数据时，当链表长度 &gt; 该值时，</span></span><br><span class="line"><span class="comment">  则将链表转换成红黑树</span></span><br><span class="line"><span class="comment">  */</span></span><br><span class="line">  <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> TREEIFY_THRESHOLD = <span class="number">8</span>; </span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">  1、桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据</span></span><br><span class="line"><span class="comment">  存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内节点数量 &lt; 6时，则将 红黑树转换</span></span><br><span class="line"><span class="comment">  成链表</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line">  <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> UNTREEIFY_THRESHOLD = <span class="number">6</span>;</span><br><span class="line"></span><br><span class="line">  <span class="comment">/*</span></span><br><span class="line"><span class="comment">  1、最小树形化容量阈值：即 当哈希表中的容量 &gt; 该值时，才允许树形化链表 （即 将链表 转换成红黑树）。</span></span><br><span class="line"><span class="comment">  否则，若 （单链表）桶内元素太多时，则直接扩容，而不是树形化。</span></span><br><span class="line"><span class="comment">  2、为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD</span></span><br><span class="line"><span class="comment">  */</span></span><br><span class="line">  <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> MIN_TREEIFY_CAPACITY = <span class="number">64</span>;</span><br><span class="line"> </span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h1 id="构造函数源码"><a href="#构造函数源码" class="headerlink" title="构造函数源码"></a>构造函数源码</h1><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">HashMap</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt;</span></span><br><span class="line"><span class="class">    <span class="keyword">extends</span> <span class="title">AbstractMap</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt;</span></span><br><span class="line"><span class="class">    <span class="keyword">implements</span> <span class="title">Map</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt;, <span class="title">Cloneable</span>, <span class="title">Serializable</span></span>&#123;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.loadFactor = DEFAULT_LOAD_FACTOR;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">(<span class="keyword">int</span> initialCapacity)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>(initialCapacity, DEFAULT_LOAD_FACTOR);</span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 构造函数3：指定&quot;容量大小&quot;和&quot;加载因子&quot;的构造函数</span></span><br><span class="line"><span class="comment">     * 加载因子和容量由自己指定</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">(<span class="keyword">int</span> initialCapacity, <span class="keyword">float</span> loadFactor)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    	<span class="comment">// 指定初始容量必须非负，否则报错  </span></span><br><span class="line">   		 <span class="keyword">if</span> (initialCapacity &lt; <span class="number">0</span>)  </span><br><span class="line">           <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Illegal initial capacity: &quot;</span> +  </span><br><span class="line">                                           initialCapacity); </span><br><span class="line"></span><br><span class="line">        <span class="comment">// HashMap的最大容量只能是MAXIMUM_CAPACITY，哪怕传入的 &gt; 最大容量</span></span><br><span class="line">        <span class="keyword">if</span> (initialCapacity &gt; MAXIMUM_CAPACITY)</span><br><span class="line">            initialCapacity = MAXIMUM_CAPACITY;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 填充比必须为正  </span></span><br><span class="line">    	<span class="keyword">if</span> (loadFactor &lt;= <span class="number">0</span> || Float.isNaN(loadFactor))  </span><br><span class="line">        	<span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Illegal load factor: &quot;</span> +  </span><br><span class="line">                                           loadFactor);  </span><br><span class="line">        <span class="comment">// 设置加载因子</span></span><br><span class="line">        <span class="keyword">this</span>.loadFactor = loadFactor;</span><br><span class="line"></span><br><span class="line">    </span><br><span class="line">        <span class="comment">/*</span></span><br><span class="line"><span class="comment">        1、设置扩容阈值</span></span><br><span class="line"><span class="comment">        2、此处不是真正的阈值，仅仅只是将传入的容量大小转化为：&gt;传入容量大小的最小的2的幂，</span></span><br><span class="line"><span class="comment">        该阈值后面会重新计算</span></span><br><span class="line"><span class="comment">        */</span></span><br><span class="line">        <span class="keyword">this</span>.threshold = tableSizeFor(initialCapacity); </span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">(Map&lt;? extends K, ? extends V&gt; m)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.loadFactor = DEFAULT_LOAD_FACTOR; </span><br><span class="line"></span><br><span class="line">        <span class="comment">// 将传入的子Map中的全部元素逐个添加到HashMap中</span></span><br><span class="line">        putMapEntries(m, <span class="keyword">false</span>); </span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="tableSizeFor"><a href="#tableSizeFor" class="headerlink" title="tableSizeFor()"></a>tableSizeFor()</h2><figure class="highlight java"><table><tr><td class="code"><pre><span class="line">  <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 作用：将传入的容量大小转化为：&gt;传入容量大小的最小的2的幂</span></span><br><span class="line"><span class="comment">     * 与JDK 1.7对比：类似于JDK 1.7 中 inflateTable()里的 roundUpToPowerOf2(toSize)</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">tableSizeFor</span><span class="params">(<span class="keyword">int</span> cap)</span> </span>&#123;</span><br><span class="line">     <span class="keyword">int</span> n = cap - <span class="number">1</span>;</span><br><span class="line">     n |= n &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line">     n |= n &gt;&gt;&gt; <span class="number">2</span>;</span><br><span class="line">     n |= n &gt;&gt;&gt; <span class="number">4</span>;</span><br><span class="line">     n |= n &gt;&gt;&gt; <span class="number">8</span>;</span><br><span class="line">     n |= n &gt;&gt;&gt; <span class="number">16</span>;</span><br><span class="line">     <span class="keyword">return</span> (n &lt; <span class="number">0</span>) ? <span class="number">1</span> : (n &gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + <span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">test</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> n = <span class="number">65538</span>;  <span class="comment">//这个数字是2^16 + 2</span></span><br><span class="line">        System.out.println(<span class="string">&quot;开始:&quot;</span> + Integer.toBinaryString(n));</span><br><span class="line">        <span class="keyword">int</span> res = tableSizeFor(n);</span><br><span class="line">        System.out.println(<span class="string">&quot;最终结果:&quot;</span> + res);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> MAXIMUM_CAPACITY = <span class="number">1</span> &lt;&lt; <span class="number">30</span>;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">tableSizeFor</span><span class="params">(<span class="keyword">int</span> cap)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> n = cap - <span class="number">1</span>;</span><br><span class="line">        n |= n &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line">        System.out.println(Integer.toBinaryString(n));</span><br><span class="line">        n |= n &gt;&gt;&gt; <span class="number">2</span>;</span><br><span class="line">        System.out.println(Integer.toBinaryString(n));</span><br><span class="line">        n |= n &gt;&gt;&gt; <span class="number">4</span>;</span><br><span class="line">        System.out.println(Integer.toBinaryString(n));</span><br><span class="line">        n |= n &gt;&gt;&gt; <span class="number">8</span>;</span><br><span class="line">        System.out.println(Integer.toBinaryString(n));</span><br><span class="line">        n |= n &gt;&gt;&gt; <span class="number">16</span>;</span><br><span class="line">        System.out.println(Integer.toBinaryString(n));</span><br><span class="line">        <span class="keyword">return</span> (n &lt; <span class="number">0</span>) ? <span class="number">1</span> : (n &gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<p>输出结果：</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">开始:10000000000000010</span><br><span class="line">11000000000000001</span><br><span class="line">11110000000000001</span><br><span class="line">11111111000000001</span><br><span class="line">11111111111111111</span><br><span class="line">11111111111111111</span><br><span class="line">最终结果:131072</span><br><span class="line"></span><br><span class="line">Process finished with exit code 0</span><br></pre></td></tr></table></figure>

<p><strong>第一次运行：</strong><br>    10000000000000010        n &gt;&gt;&gt; 1;<br>    01000000000000000        进行|运算<br>    11000000000000001<br>分析：<br>    把最大位的1，通过位移后移一位，并且通过|运算，组合起来</p>
<p><strong>第二次运行：</strong><br>    11000000000000001        n &gt;&gt;&gt; 2;<br>    00110000000000000        进行|运算<br>    11110000000000001<br>分析：<br>    把最大的两位，已经变成1的，往后移动两位，并且通过|运算，组合起来</p>
<p><strong>第三次运行：</strong><br>    11110000000000001        n &gt;&gt;&gt; 4;<br>    00001111000000000        进行|运算<br>    11111111000000001<br>分析：<br>    把最大4位，已经变成1的，往后移动4位，并且通过|运算，组合起来</p>
<p><strong>第四次运行：</strong><br>    11111111000000001        n &gt;&gt;&gt; 8;<br>    00000000111111110        进行|运算<br>    11111111111111111<br>分析：<br>    把最大的8位，已经变成1的，往后移动8位，并且通过|运算，组合起来</p>
<p><strong>第五次运算：</strong><br>    同上。因为我的数据，最大只到17位，所有第五次没有效果。可以用32位来进行运算，第五次是通过前16位已经变成1的数据，往后移动16位，然后通过或运算，最后的结果是32位都变成1。</p>
<blockquote>
<p>原理就是，保证造成一个所有位都为1的数据。并且通过最后的+1。变成2^N次方的数据。</p>
</blockquote>
<h1 id="put源码"><a href="#put源码" class="headerlink" title="put源码"></a>put源码</h1><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> V <span class="title">put</span><span class="params">(K key, V value)</span> </span>&#123;</span><br><span class="line">       <span class="comment">//在第一个参数里就直接计算出了hash值</span></span><br><span class="line">       <span class="keyword">return</span> putVal(hash(key), key, value, <span class="keyword">false</span>, <span class="keyword">true</span>);</span><br><span class="line">   &#125;</span><br></pre></td></tr></table></figure>



<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">final</span> V <span class="title">putVal</span><span class="params">(<span class="keyword">int</span> hash, K key, V value, <span class="keyword">boolean</span> onlyIfAbsent,</span></span></span><br><span class="line"><span class="function"><span class="params">                  <span class="keyword">boolean</span> evict)</span> </span>&#123;</span><br><span class="line">       Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; <span class="keyword">int</span> n, i;</span><br><span class="line">       </span><br><span class="line">       </span><br><span class="line">       <span class="comment">/*</span></span><br><span class="line"><span class="comment">       1、若哈希表的数组tab为空，则通过resize()进行初始化，所以，初始化哈希表的时机就是第1次</span></span><br><span class="line"><span class="comment">       调用put函数时，即调用resize() 初始化创建。</span></span><br><span class="line"><span class="comment">       */</span></span><br><span class="line">       <span class="keyword">if</span> ((tab = table) == <span class="keyword">null</span> || (n = tab.length) == <span class="number">0</span>)</span><br><span class="line">           n = (tab = resize()).length;</span><br><span class="line">       </span><br><span class="line">       <span class="comment">/* if分支</span></span><br><span class="line"><span class="comment">       1、根据键值key计算的hash值，计算插入存储的数组索引i</span></span><br><span class="line"><span class="comment">   	2、插入时，需判断是否存在Hash冲突：</span></span><br><span class="line"><span class="comment">   	  2-1、若不存在（即当前table[i] == null），则直接在该数组位置新建节点，插入完毕。</span></span><br><span class="line"><span class="comment">   	  2-2、否则代表发生hash冲突，进入else分支</span></span><br><span class="line"><span class="comment">       */</span></span><br><span class="line">       <span class="keyword">if</span> ((p = tab[i = (n - <span class="number">1</span>) &amp; hash]) == <span class="keyword">null</span>)</span><br><span class="line">           tab[i] = newNode(hash, key, value, <span class="keyword">null</span>);</span><br><span class="line">       </span><br><span class="line">       <span class="keyword">else</span> &#123;</span><br><span class="line">           Node&lt;K,V&gt; e; K k;</span><br><span class="line">          <span class="comment">//判断 table[i]的元素的key是否与需插入的key一样，若相同则直接用新value覆盖旧value</span></span><br><span class="line">           <span class="comment">//【即更新操作】</span></span><br><span class="line">           <span class="keyword">if</span> (p.hash == hash &amp;&amp;</span><br><span class="line">               ((k = p.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">               e = p;</span><br><span class="line">           </span><br><span class="line">           <span class="comment">//继续判断：需插入的数据结构是否为红黑树or链表。若是红黑树，则直接在树中插入or更新键值对     </span></span><br><span class="line">           <span class="keyword">else</span> <span class="keyword">if</span> (p <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">               <span class="comment">/*</span></span><br><span class="line"><span class="comment">               1、putTreeVal作用：向红黑树插入 or 更新数据（键值对）</span></span><br><span class="line"><span class="comment">     			2、过程：遍历红黑树判断该节点的key是否与需插入的key是否相同：</span></span><br><span class="line"><span class="comment">          		   2-1、若相同，则新value覆盖旧value</span></span><br><span class="line"><span class="comment">          		   2-2、若不相同，则插入</span></span><br><span class="line"><span class="comment">               */</span></span><br><span class="line">               e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(<span class="keyword">this</span>, tab, hash, key, value);</span><br><span class="line">           </span><br><span class="line">           <span class="comment">//进入到这个分支说明是链表节点</span></span><br><span class="line">           <span class="keyword">else</span> &#123;</span><br><span class="line">               <span class="comment">/*</span></span><br><span class="line"><span class="comment">               过程：</span></span><br><span class="line"><span class="comment">               1、遍历table[i]，判断Key是否已存在：采用equals()对比当前遍历节点的key 与</span></span><br><span class="line"><span class="comment">               需插入数据的key：若已存在，则直接用新value覆盖旧value</span></span><br><span class="line"><span class="comment">      		   2、遍历完毕后仍无发现上述情况，则直接在链表尾部插入数据(尾插法)</span></span><br><span class="line"><span class="comment">      		   3、新增节点后，需判断链表长度是否&gt;8（8 = 桶的树化阈值）：若是，则把链表转换为红黑树</span></span><br><span class="line"><span class="comment">               */</span></span><br><span class="line">               <span class="keyword">for</span> (<span class="keyword">int</span> binCount = <span class="number">0</span>; ; ++binCount) &#123;</span><br><span class="line">                   <span class="comment">//对于2情况的操作  尾插法插入尾部</span></span><br><span class="line">                   <span class="keyword">if</span> ((e = p.next) == <span class="keyword">null</span>) &#123;</span><br><span class="line">                       p.next = newNode(hash, key, value, <span class="keyword">null</span>);</span><br><span class="line">                       <span class="comment">//对于3情况的操作</span></span><br><span class="line">                       <span class="keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - <span class="number">1</span>) <span class="comment">// -1 for 1st</span></span><br><span class="line">                           treeifyBin(tab, hash);</span><br><span class="line">                       <span class="keyword">break</span>;</span><br><span class="line">                   &#125;</span><br><span class="line">                   <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                       ((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                       <span class="keyword">break</span>;</span><br><span class="line">                   p = e;</span><br><span class="line">               &#125;</span><br><span class="line">           &#125;</span><br><span class="line">           <span class="comment">// 对1情况的后续操作：发现key已存在，直接用新value 覆盖 旧value，返回旧value</span></span><br><span class="line">           <span class="keyword">if</span> (e != <span class="keyword">null</span>) &#123; <span class="comment">// existing mapping for key</span></span><br><span class="line">               V oldValue = e.value;</span><br><span class="line">               <span class="keyword">if</span> (!onlyIfAbsent || oldValue == <span class="keyword">null</span>)</span><br><span class="line">                   e.value = value;</span><br><span class="line">               afterNodeAccess(e);</span><br><span class="line">               <span class="keyword">return</span> oldValue;</span><br><span class="line">           &#125;</span><br><span class="line">       &#125;</span><br><span class="line">       ++modCount;</span><br><span class="line">       <span class="comment">// 插入成功后，判断实际存在的键值对数量size &gt; threshold</span></span><br><span class="line">       <span class="keyword">if</span> (++size &gt; threshold)</span><br><span class="line">           resize();</span><br><span class="line">       afterNodeInsertion(evict);</span><br><span class="line">       <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">   &#125;</span><br></pre></td></tr></table></figure>



<h2 id="hash"><a href="#hash" class="headerlink" title="hash()"></a>hash()</h2><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"></span><br><span class="line"> <span class="comment">//JDK7实现:使用hashCode() + 4次位运算 + 5次异或运算（9次扰动）</span></span><br><span class="line"><span class="function"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">hash</span><span class="params">(<span class="keyword">int</span> h)</span> </span>&#123;</span><br><span class="line">   h ^= k.hashCode(); </span><br><span class="line">   h ^= (h &gt;&gt;&gt; <span class="number">20</span>) ^ (h &gt;&gt;&gt; <span class="number">12</span>);</span><br><span class="line">   <span class="keyword">return</span> h ^ (h &gt;&gt;&gt; <span class="number">7</span>) ^ (h &gt;&gt;&gt; <span class="number">4</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"> <span class="comment">//JDK8实现: 使用hashCode() + 1次位运算 + 1次异或运算（2次扰动） </span></span><br><span class="line"> <span class="function"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">hash</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">      <span class="keyword">int</span> h;</span><br><span class="line">     <span class="comment">/*</span></span><br><span class="line"><span class="comment">     1、当key = null时，hash值 = 0，所以HashMap的key可为null      </span></span><br><span class="line"><span class="comment">  2、当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后对哈希码进行扰动处理。</span></span><br><span class="line"><span class="comment">  高位参与低位的运算：h ^ (h &gt;&gt;&gt; 16) </span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">     <span class="keyword">return</span> (key == <span class="keyword">null</span>) ? <span class="number">0</span> : (h = key.hashCode()) ^ (h &gt;&gt;&gt; <span class="number">16</span>);</span><br><span class="line">       </span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<p>JDK8 hash的运算原理：高位参与低位运算，使得hash更加均匀。</p>
<img src= "" data-lazy-src="https://upyunimg.imlql.cn/youthlql@1.0.8/Java_collection/HashMap/JDK8/0002.png">





<h2 id="resize"><a href="#resize" class="headerlink" title="resize()"></a>resize()</h2><p>这个方法改动比较大</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">   </span><br><span class="line">   <span class="comment">//该函数有2种使用情况：1、初始化哈希表 2、当前数组容量过小，需扩容   </span></span><br><span class="line">   <span class="keyword">final</span> Node&lt;K,V&gt;[] resize() &#123;</span><br><span class="line">    Node&lt;K,V&gt;[] oldTab = table; <span class="comment">// 扩容前的数组（当前数组）</span></span><br><span class="line">    <span class="keyword">int</span> oldCap = (oldTab == <span class="keyword">null</span>) ? <span class="number">0</span> : oldTab.length; <span class="comment">// 扩容前的数组的容量</span></span><br><span class="line">    <span class="keyword">int</span> oldThr = threshold;<span class="comment">// 扩容前的数组的阈值</span></span><br><span class="line">    <span class="keyword">int</span> newCap, newThr = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 针对情况2：若扩容前的数组容量超过最大值，则不再扩充</span></span><br><span class="line">    <span class="keyword">if</span> (oldCap &gt; <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span> (oldCap &gt;= MAXIMUM_CAPACITY) &#123;</span><br><span class="line">            threshold = Integer.MAX_VALUE;</span><br><span class="line">            <span class="keyword">return</span> oldTab;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 针对情况2：若无超过最大值，就扩充为原来的2倍</span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> ((newCap = oldCap &lt;&lt; <span class="number">1</span>) &lt; MAXIMUM_CAPACITY &amp;&amp;</span><br><span class="line">                 oldCap &gt;= DEFAULT_INITIAL_CAPACITY)</span><br><span class="line">            newThr = oldThr &lt;&lt; <span class="number">1</span>; <span class="comment">// 通过右移扩充2倍</span></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 针对情况1：初始化哈希表（采用指定值或者默认值）</span></span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span> (oldThr &gt; <span class="number">0</span>) </span><br><span class="line">        newCap = oldThr;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">else</span> &#123;  </span><br><span class="line">        newCap = DEFAULT_INITIAL_CAPACITY;</span><br><span class="line">        newThr = (<span class="keyword">int</span>)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 计算新的扩容阈值</span></span><br><span class="line">    <span class="keyword">if</span> (newThr == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">float</span> ft = (<span class="keyword">float</span>)newCap * loadFactor;</span><br><span class="line">        newThr = (newCap &lt; MAXIMUM_CAPACITY &amp;&amp; ft &lt; (<span class="keyword">float</span>)MAXIMUM_CAPACITY ?</span><br><span class="line">                  (<span class="keyword">int</span>)ft : Integer.MAX_VALUE);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    threshold = newThr;</span><br><span class="line">    <span class="meta">@SuppressWarnings(&#123;&quot;rawtypes&quot;,&quot;unchecked&quot;&#125;)</span></span><br><span class="line">        Node&lt;K,V&gt;[] newTab = (Node&lt;K,V&gt;[])<span class="keyword">new</span> Node[newCap];</span><br><span class="line">    table = newTab;</span><br><span class="line">	</span><br><span class="line">    <span class="comment">//旧数组数据移动到新数组里，整体过程也是遍历旧数组每个数据</span></span><br><span class="line">    <span class="keyword">if</span> (oldTab != <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="comment">// 把每个bucket都移动到新的buckets中</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; oldCap; ++j) &#123;</span><br><span class="line">            Node&lt;K,V&gt; e;</span><br><span class="line">            <span class="keyword">if</span> ((e = oldTab[j]) != <span class="keyword">null</span>) &#123;</span><br><span class="line">                oldTab[j] = <span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">                <span class="keyword">if</span> (e.next == <span class="keyword">null</span>)</span><br><span class="line">                    newTab[e.hash &amp; (newCap - <span class="number">1</span>)] = e;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> (e <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                    ((TreeNode&lt;K,V&gt;)e).split(<span class="keyword">this</span>, newTab, j, oldCap);</span><br><span class="line"></span><br><span class="line">                <span class="keyword">else</span> &#123; <span class="comment">// 链表优化重hash的代码块</span></span><br><span class="line">                    Node&lt;K,V&gt; loHead = <span class="keyword">null</span>, loTail = <span class="keyword">null</span>;</span><br><span class="line">                    Node&lt;K,V&gt; hiHead = <span class="keyword">null</span>, hiTail = <span class="keyword">null</span>;</span><br><span class="line">                    Node&lt;K,V&gt; next;</span><br><span class="line">                    <span class="comment">//这个待会细讲</span></span><br><span class="line">                    <span class="keyword">do</span> &#123;</span><br><span class="line">                        next = e.next;</span><br><span class="line">                        <span class="comment">//原索引</span></span><br><span class="line">                        <span class="keyword">if</span> ((e.hash &amp; oldCap) == <span class="number">0</span>) &#123;</span><br><span class="line">                            <span class="keyword">if</span> (loTail == <span class="keyword">null</span>)</span><br><span class="line">                                loHead = e;</span><br><span class="line">                            <span class="keyword">else</span></span><br><span class="line">                                loTail.next = e;</span><br><span class="line">                            loTail = e;</span><br><span class="line">                        &#125;</span><br><span class="line">                        <span class="comment">// 原索引 + oldCap</span></span><br><span class="line">                        <span class="keyword">else</span> &#123;</span><br><span class="line">                            <span class="keyword">if</span> (hiTail == <span class="keyword">null</span>)</span><br><span class="line">                                hiHead = e;</span><br><span class="line">                            <span class="keyword">else</span></span><br><span class="line">                                hiTail.next = e;</span><br><span class="line">                            hiTail = e;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125; <span class="keyword">while</span> ((e = next) != <span class="keyword">null</span>);</span><br><span class="line">                    <span class="comment">// 原索引放到bucket里</span></span><br><span class="line">                    <span class="keyword">if</span> (loTail != <span class="keyword">null</span>) &#123;</span><br><span class="line">                        loTail.next = <span class="keyword">null</span>;</span><br><span class="line">                        newTab[j] = loHead;</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="comment">// 原索引+oldCap放到bucket里</span></span><br><span class="line">                    <span class="keyword">if</span> (hiTail != <span class="keyword">null</span>) &#123;</span><br><span class="line">                        hiTail.next = <span class="keyword">null</span>;</span><br><span class="line">                        newTab[j + oldCap] = hiHead;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> newTab;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<p>JDK8扩容时，数据在数组下标的计算方式</p>
<img src= "" data-lazy-src="https://upyunimg.imlql.cn/youthlql@1.0.8/Java_collection/HashMap/JDK8/0003.png">

<ul>
<li><code>JDK8</code>根据此结论作出的新元素存储位置计算规则非常简单，提高了扩容效率。</li>
</ul>
<ul>
<li>这与 <code>JDK7</code>在计算新元素的存储位置有很大区别：<code>JDK7</code>在扩容后，都需按照原来方法进行rehash，效率不高。</li>
</ul>
<h1 id="get源码"><a href="#get源码" class="headerlink" title="get源码"></a>get源码</h1><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"></span><br><span class="line">   <span class="function"><span class="keyword">public</span> V <span class="title">get</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">    Node&lt;K,V&gt; e;</span><br><span class="line">    <span class="comment">// 计算需获取数据的hash值,通过getNode（）获取所查询的数据,获取后，判断数据是否为空</span></span><br><span class="line">    <span class="keyword">return</span> (e = getNode(hash(key), key)) == <span class="keyword">null</span> ? <span class="keyword">null</span> : e.value;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">final</span> Node&lt;K,V&gt; <span class="title">getNode</span><span class="params">(<span class="keyword">int</span> hash, Object key)</span> </span>&#123;</span><br><span class="line">    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first, e; <span class="keyword">int</span> n; K k;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//计算存放在数组table中的位置</span></span><br><span class="line">    <span class="keyword">if</span> ((tab = table) != <span class="keyword">null</span> &amp;&amp; (n = tab.length) &gt; <span class="number">0</span> &amp;&amp;</span><br><span class="line">        (first = tab[(n - <span class="number">1</span>) &amp; hash]) != <span class="keyword">null</span>) &#123;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 先在数组中找，若存在，则直接返回</span></span><br><span class="line">        <span class="keyword">if</span> (first.hash == hash &amp;&amp; <span class="comment">// always check first node</span></span><br><span class="line">            ((k = first.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">            <span class="keyword">return</span> first;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//若数组中没有，则到红黑树中寻找</span></span><br><span class="line">        <span class="keyword">if</span> ((e = first.next) != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="comment">// 在树中get</span></span><br><span class="line">            <span class="keyword">if</span> (first <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                <span class="keyword">return</span> ((TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);</span><br><span class="line"></span><br><span class="line">            <span class="comment">//若红黑树中也没有，则通过遍历，到链表中寻找</span></span><br><span class="line">            <span class="keyword">do</span> &#123;</span><br><span class="line">                <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                    ((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                    <span class="keyword">return</span> e;</span><br><span class="line">            &#125; <span class="keyword">while</span> ((e = e.next) != <span class="keyword">null</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>





<h1 id="—下面是常见面试题—"><a href="#—下面是常见面试题—" class="headerlink" title="—下面是常见面试题—"></a>—下面是常见面试题—</h1><h1 id="HashMap在JDK7和8中区别？"><a href="#HashMap在JDK7和8中区别？" class="headerlink" title="HashMap在JDK7和8中区别？"></a>HashMap在JDK7和8中区别？</h1><p>1、hash冲突时：JDK7用的是头插法，而JDK1.8及之后使用的都是尾插法。JDK7是用单链表进行的纵向延伸，当采用头插法时会容易出现逆序且环形链表死循环问题。但是在JDK8之后是使用尾插法，能够避免出现逆序且链表死循环的问题。</p>
<p>2、扩容时：JDK7需要重新进行rehash。JDK8则直接时判断hash值新参与的位是0还是1，0就是原位置，1就是原位置+就容量</p>
<p>3、引入了红黑树（原因前面说过）</p>
<p>4、hash的计算：JDK7是9次扰动（4次位运算 + 5次异或运算），JDK8时是2次扰动（1次位运算 + 1次异或运算）。</p>
<p>5、JDK7是先扩容再插入k-v，JDK8时是插入后一起扩容。</p>
<h1 id="为什么不直接用hash码作为数组table的下标？"><a href="#为什么不直接用hash码作为数组table的下标？" class="headerlink" title="为什么不直接用hash码作为数组table的下标？"></a>为什么不直接用hash码作为数组table的下标？</h1><p>1、哈希码一般是int型，范围是-(2^31) – 2^31 - 1。容易出现哈希码与数组大小范围不匹配的情况，即计算出来的哈希码可能不在数组大小范围内，从而导致无法匹配存储位置。</p>
<p>2、常见解决办法就是hash值与数组长度取模。</p>
<h1 id="为什么容量要求为2的幂？"><a href="#为什么容量要求为2的幂？" class="headerlink" title="为什么容量要求为2的幂？"></a>为什么容量要求为2的幂？</h1><p>一般来说散列表容量的常规设计思路是容量取素数，因为素数导致冲突的概率 &lt; 合数。比如Hashtable初始化容量就是11（不过扩容后不能保证是素数）</p>
<p><strong>hashmap这样设计的原因是</strong></p>
<p>1、保证哈希码的均匀性。首先容量可为奇数，也可为偶数。假设数组长度为奇数，那么二进制最后一位是1。假设数组长度为偶数，那么二进制最后一位是0。如果是奇数  hash&amp;(length - 1) 铁定是偶数，就会导致浪费了数组的一半位置（奇数索引无法被放数据，hash冲突概率高）。如果是2的幂这种偶数，length - 1就是奇数，那么最终的hash&amp;(length-1)计算出来的索引位置取决于hash值，也就是说可以是偶数索引，也可以是奇数索引，均匀分布。</p>
<p>2、length是2的幂时 hash&amp;(length - 1)等价于hash % length。但是&amp;效率更高，而只有length是2的幂，这两个才等价。</p>
<h1 id="二次扰动的好处"><a href="#二次扰动的好处" class="headerlink" title="二次扰动的好处"></a>二次扰动的好处</h1><p>高位充分参与低位运算，加大哈希码低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性 &amp; 均匀性，最终减少Hash冲突</p>
<h1 id="什么样类型的数据适合做hashmap的key"><a href="#什么样类型的数据适合做hashmap的key" class="headerlink" title="什么样类型的数据适合做hashmap的key?"></a>什么样类型的数据适合做hashmap的key?</h1><p>像Integer这种，内部属性value被final修饰，保证了Hash值的不可更改性，有效的减少了hash冲突</p>
<h1 id="为什么选择8作为树化阈值？"><a href="#为什么选择8作为树化阈值？" class="headerlink" title="为什么选择8作为树化阈值？"></a>为什么选择8作为树化阈值？</h1><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//Java8代码官方解释的原因</span></span><br><span class="line">  * Because TreeNodes are about twice the size of regular nodes, we</span><br><span class="line">    * use them only when bins contain enough nodes to warrant use</span><br><span class="line">    * (see TREEIFY_THRESHOLD). <span class="function">And when they become too <span class="title">small</span> <span class="params">(due to</span></span></span><br><span class="line"><span class="function"><span class="params">    * removal or resizing)</span> they are converted back to plain bins.  In</span></span><br><span class="line"><span class="function">    * usages with well-distributed user hashCodes, tree bins are</span></span><br><span class="line"><span class="function">    * rarely used.  Ideally, under random hashCodes, the frequency of</span></span><br><span class="line"><span class="function">    * nodes in bins follows a Poisson distribution</span></span><br><span class="line"><span class="function">    * <span class="params">(http://en.wikipedia.org/wiki/Poisson_distribution)</span> with a</span></span><br><span class="line"><span class="function">    * parameter of about 0.5 on average <span class="keyword">for</span> the <span class="keyword">default</span> resizing</span></span><br><span class="line"><span class="function">    * threshold of 0.75, although with a large variance because of</span></span><br><span class="line"><span class="function">    * resizing granularity. Ignoring variance, the expected</span></span><br><span class="line"><span class="function">    * occurrences of list size k <span class="title">are</span> <span class="params">(exp(-<span class="number">0.5</span>)</span> * <span class="title">pow</span><span class="params">(<span class="number">0.5</span>, k)</span> /</span></span><br><span class="line"><span class="function">    * <span class="title">factorial</span><span class="params">(k)</span>). The first values are:</span></span><br><span class="line"><span class="function">    *</span></span><br><span class="line"><span class="function">    * 0:    0.60653066</span></span><br><span class="line"><span class="function">    * 1:    0.30326533</span></span><br><span class="line"><span class="function">    * 2:    0.07581633</span></span><br><span class="line"><span class="function">    * 3:    0.01263606</span></span><br><span class="line"><span class="function">    * 4:    0.00157952</span></span><br><span class="line"><span class="function">    * 5:    0.00015795</span></span><br><span class="line"><span class="function">    * 6:    0.00001316</span></span><br><span class="line"><span class="function">    * 7:    0.00000094</span></span><br><span class="line"><span class="function">    * 8:    0.00000006</span></span><br><span class="line"><span class="function">    * more: less than 1 in ten million</span></span><br><span class="line"><span class="function"></span></span><br></pre></td></tr></table></figure>

<p>由于treenodes的大小大约是常规节点的两倍，因此我们仅在容器包含足够的节点以保证使用时才使用它们，当它们变得太小（由于移除或调整大小）时，它们会被转换回普通的node节点，容器中节点分布在hash桶中的频率遵循泊松分布，桶的长度超过8的概率非常非常小，作者是根据概率统计而选择了8作为阀值。</p>
<h1 id="为什么选择6和8作为链表化和树化的阈值"><a href="#为什么选择6和8作为链表化和树化的阈值" class="headerlink" title="为什么选择6和8作为链表化和树化的阈值?"></a>为什么选择6和8作为链表化和树化的阈值?</h1><p>1、首先就是遵循泊松分布概率选了6和8</p>
<p>2、其次：如果选择6和8（如果链表小于等于6树还原转为链表，大于等于8转为树），中间有个差值7可以有效防止链表和树频繁转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。</p>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="mailto:undefined">youthlql</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://imlql.cn/post/cbc5672a.html">https://imlql.cn/post/cbc5672a.html</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://imlql.cn" target="_blank">风祈的时光录</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/Java%E9%9B%86%E5%90%88/">Java集合</a><a class="post-meta__tags" href="/tags/HashMap/">HashMap</a></div><div class="post_share"></div></div><div class="post-reward"><div class="reward-button"><i class="fas fa-qrcode"></i> 打赏</div><div class="reward-main"><ul class="reward-all"><li class="reward-item"><a href="https://npm.elemecdn.com/youthlql@1.0.8/blog/wechat.jpg" target="_blank"><img class="post-qr-code-img" src= "" data-lazy-src="https://npm.elemecdn.com/youthlql@1.0.8/blog/wechat.jpg" alt="微信"/></a><div class="post-qr-code-desc">微信</div></li><li class="reward-item"><a href="https://npm.elemecdn.com/youthlql@1.0.8/blog/alipay.jpg" target="_blank"><img class="post-qr-code-img" src= "" data-lazy-src="https://npm.elemecdn.com/youthlql@1.0.8/blog/alipay.jpg" alt="支付宝"/></a><div class="post-qr-code-desc">支付宝</div></li></ul></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/post/8c954c6.html"><img class="prev-cover" src= "" data-lazy-src="https://upyunimg.imlql.cn/lql_static@latest/logo/jvm.png" onerror="onerror=null;src='/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">JVM系列-第1章-JVM与Java体系结构</div></div></a></div><div class="next-post pull-right"><a href="/post/f1f58db2.html"><img class="next-cover" src= "" data-lazy-src="https://upyunimg.imlql.cn/lql_static@latest/logo/java.png" onerror="onerror=null;src='/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">HashMap-JDK7源码讲解</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span>相关推荐</span></div><div class="relatedPosts-list"><div><a href="/post/f1f58db2.html" title="HashMap-JDK7源码讲解"><img class="cover" src= "" data-lazy-src="https://upyunimg.imlql.cn/lql_static@latest/logo/java.png" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2020-11-01</div><div class="title">HashMap-JDK7源码讲解</div></div></a></div></div></div></div><div class="aside-content" id="aside-content"><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content is-expand"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="toc-text">数据结构</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%BA%A2%E9%BB%91%E6%A0%91"><span class="toc-text">红黑树</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E8%A6%81%E5%BC%95%E5%85%A5%E7%BA%A2%E9%BB%91%E6%A0%91"><span class="toc-text">为什么要引入红黑树</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Node%E7%B1%BB"><span class="toc-text">Node类</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#TreeNode%E7%B1%BB"><span class="toc-text">TreeNode类</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%87%8D%E8%A6%81%E5%8F%82%E6%95%B0"><span class="toc-text">重要参数</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%9E%84%E9%80%A0%E5%87%BD%E6%95%B0%E6%BA%90%E7%A0%81"><span class="toc-text">构造函数源码</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#tableSizeFor"><span class="toc-text">tableSizeFor()</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#put%E6%BA%90%E7%A0%81"><span class="toc-text">put源码</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#hash"><span class="toc-text">hash()</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#resize"><span class="toc-text">resize()</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#get%E6%BA%90%E7%A0%81"><span class="toc-text">get源码</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E2%80%94%E4%B8%8B%E9%9D%A2%E6%98%AF%E5%B8%B8%E8%A7%81%E9%9D%A2%E8%AF%95%E9%A2%98%E2%80%94"><span class="toc-text">—下面是常见面试题—</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#HashMap%E5%9C%A8JDK7%E5%92%8C8%E4%B8%AD%E5%8C%BA%E5%88%AB%EF%BC%9F"><span class="toc-text">HashMap在JDK7和8中区别？</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E4%B8%8D%E7%9B%B4%E6%8E%A5%E7%94%A8hash%E7%A0%81%E4%BD%9C%E4%B8%BA%E6%95%B0%E7%BB%84table%E7%9A%84%E4%B8%8B%E6%A0%87%EF%BC%9F"><span class="toc-text">为什么不直接用hash码作为数组table的下标？</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E5%AE%B9%E9%87%8F%E8%A6%81%E6%B1%82%E4%B8%BA2%E7%9A%84%E5%B9%82%EF%BC%9F"><span class="toc-text">为什么容量要求为2的幂？</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%BA%8C%E6%AC%A1%E6%89%B0%E5%8A%A8%E7%9A%84%E5%A5%BD%E5%A4%84"><span class="toc-text">二次扰动的好处</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%BB%80%E4%B9%88%E6%A0%B7%E7%B1%BB%E5%9E%8B%E7%9A%84%E6%95%B0%E6%8D%AE%E9%80%82%E5%90%88%E5%81%9Ahashmap%E7%9A%84key"><span class="toc-text">什么样类型的数据适合做hashmap的key?</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E9%80%89%E6%8B%A98%E4%BD%9C%E4%B8%BA%E6%A0%91%E5%8C%96%E9%98%88%E5%80%BC%EF%BC%9F"><span class="toc-text">为什么选择8作为树化阈值？</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E9%80%89%E6%8B%A96%E5%92%8C8%E4%BD%9C%E4%B8%BA%E9%93%BE%E8%A1%A8%E5%8C%96%E5%92%8C%E6%A0%91%E5%8C%96%E7%9A%84%E9%98%88%E5%80%BC"><span class="toc-text">为什么选择6和8作为链表化和树化的阈值?</span></a></li></ol></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">&copy;2020 - 2023 By youthlql</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div><div class="footer_custom_text"><a href="https://www.upyun.com/?utm_source=lianmeng&utm_medium=referral" target="_blank" rel="noopener" class="one-pan-link-mark"><img style="position:relative;top:-3px; " src= "" data-lazy-src="https://npm.elemecdn.com/lql_static@latest/upyun/logo.png" align="absmiddle" width="60px" height="30px"></a><a target="_blank" rel="noopener" href="https://beian.miit.gov.cn"><img class="icp-icon" src= "" data-lazy-src="https://npm.elemecdn.com/lql_static@latest/logo/icp.png"><span>鄂ICP备19028890号</span></a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="translateLink" type="button" title="简繁转换">简</button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">本地搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="fas fa-times"></i></button></nav><div class="is-center" id="loading-database"><i class="fas fa-spinner fa-pulse"></i><span>  数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"/></div></div><hr/><div id="local-search-results"></div></div></div><div id="search-mask"></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="/js/tw_cn.js"></script><script src="https://npm.elemecdn.com/@fancyapps/ui/dist/fancybox.umd.js"></script><script src="https://npm.elemecdn.com/instant.page/instantpage.js" type="module"></script><script src="https://cdn.jsdelivr.net/npm/vanilla-lazyload/dist/lazyload.iife.min.js"></script><script src="/js/search/local-search.js"></script><div class="js-pjax"></div><script defer src="https://npm.elemecdn.com/jquery@latest/dist/jquery.min.js"></script></div></body></html>